package com.fengye.algorithms.alibaba;

import java.util.Arrays;
import java.util.Random;

/**
 * 水塘抽样算法，用于抽奖
 *
 * 设计一个抽奖，假定只有非常有限的内存，处理一个无限的样本流，任何时候
 * 都能提供出 N 个中奖的样本，而且所有已经遇到的样本的几率一样
 *
 * 假设数据序列的规模为 n，需要采样的数量的为 k。
 *
 * 首先构建一个可容纳 k 个元素的数组，将序列的前 k 个元素放入数组中。
 *
 * 然后从第 k+1 个元素开始，以 k/n 的概率来决定该元素是否被替换到数组中（数组中的元素被替换的概率是相同的）。
 * 当遍历完所有元素之后，数组中剩下的元素即为所需采取的样本。
 *
 * @Author fengye
 * @Date 2023/4/6 10:06
 **/
public class ReservoirSamplingMain {
    public static void main(String[] args) {
        int N = 10000;
        int K = 10;
        int[] pool = new int[N];
        Random random = new Random();
        // 初始化
        for(int i = 0; i < N; i++) {
            pool[i] = i;
        }

        int[] result = new int[K];
        // 前K个元素直接放入结果
        for(int i = 0; i < K; i++) {
            result[i] = i;
        }

        for(int i=K; i<N; i++) {
            int r = random.nextInt(i+1);
            // 在i+1的几率下随机到一个K内的记录
            if(r < K) {
                result[r] = pool[i];
            }
        }

        Arrays.stream(result).forEach(System.out::println);

    }

}
